\documentclass[UTF8]{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{ctex}
\setlength{\parindent}{2em}

\title{Week 2:使用二叉树对数组排序}

\author{唐瑞良\\ 强基工程力学 3210105852}

\begin{document}

\maketitle

\section{主要内容}
\indent 此次内容实现了通过使用二叉树完成数组排序的功能。
\section{代码实现与测试}
\indent 树的实现使用了书上的头文件，插入部分直接使用循环调用了$insert(\_arr[ii])$完成。\\
\indent 计时模块调用了$C++$的$time$库中的$clock()$函数，记录了插入开始和插入结束时的系统时间，最终表示了排序总时间。\\
\indent 打乱部分使用了$random\_shuffle$函数，并调用了$srand$结合系统时间分配随机数，使得数组被随机打乱。\\
\indent 测试部分分成了$5$个$rank$，分别代表数据个数为$10^rank$，并对每一组数据都做了$mode=0$与$mode=1$的插入，$arr$数组初始设定为$1~10^rank$顺序排列，故对于$mode=0$始终为最坏情况。运行结果如下：\\
\begin{verbatim}
Max = 10
1e-06s 0s
Max = 100
2.6e-05s 9e-06s
Max = 1000
0.002455s 0.000115s
Max = 10000
0.316837s 0.001705s
Max = 100000
36.7413s 0.03055s
\end{verbatim}
\section{结果}
\indent 结合结果与代码，估计正常排序的时间复杂度为$O(n^2)$,根据二叉树的特点、代码与运行结果，估计其平均效率为$O(nlogn)$。\\
\indent 使用gdb运行test，正常退出，说明未发生内存泄露（也许吧）。
\end{document}
